package org.labuladong.动态规划算法.DP;

import java.util.Arrays;

/**
 * @Auther: qingle
 * @Date: 2024/10/23-11:21
 * @Description: 13ms 击败75.00%
 *
 * 解释
 * 初始化：创建一个数组 dp，长度为 amount + 1，并初始化为 amount + 1（一个较大的值），表示初始状态下无法凑成该金额。
 * 基本情况：dp[0] 初始化为 0，表示凑成金额 0 需要 0 个硬币。
 * 状态转移：遍历每个金额 i，对于每个硬币 coin，如果 i - coin 是一个有效的金额（即 i - coin >= 0），则更新 dp[i] 为 dp[i - coin] + 1 和当前 dp[i] 的最小值。
 * 结果：最后返回 dp[amount]，如果 dp[amount] 仍然大于 amount，说明无法凑成该金额，返回 -1。
 *
 * @version: 1.0
 */
public class dp02_coins {

public static int coinChange(int[] coins, int amount) {
    if (coins == null || coins.length == 0 || amount < 0) {
        return -1;
    }
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // 初始化为一个较大的值
    dp[0] = 0; // 基本情况

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i - coin >= 0) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}


	public static void main(String[] args) {

		int[] coins = {1,2,5};
		int amount = 11;
		System.out.println(coinChange(coins, amount));
	}
}
